#!/usr/bin/env python
#
# Recursive Descent Parser for the Simple LISP Dialect for Teaching
#
# Author:   Mike Murphy <mamurph@cs.clemson.edu>
# Revision: 10 January 2009
#
# Copyright 2008-2009 Clemson University
#
# Permission is hereby granted, free of charge, to any person obtaining a
# copy of this software and associated documentation files (the "Software"),
# to deal in the Software without restriction, including without limitation
# the rights to use, copy, modify, merge, publish, distribute, sublicense,
# and/or sell copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
# IN THE SOFTWARE.
#
# This material is based upon work supported under a National Science
# Foundation Graduate Research Fellowship. Any opinions, findings,
# conclusions or recommendations expressed in this publication are those of
# the author(s) and do not necessarily reflect the views of the National
# Science Foundation.

import sys
from scanner import Scanner
from shared_config import SCAN_TYPES, CompilerException

# Set DEBUG to True to see parser debugging output; set TRACE to True to see
# parser trace. Note these flags affect *this module ONLY*
DEBUG=False
TRACE=False


# Debug and trace routines
def dbg(msg):
   if DEBUG:
      print >> sys.stderr, '*P:DEBUG*:', msg
#

def trace(msg):
   if TRACE:
      print >> sys.stderr, '*P:TRACE*:', msg
#


# Custom exception for parse errors
class ParserException(CompilerException):
   def __init__(self, message, line):
      CompilerException.__init__(self, 'Parse Error: unexpected ' + \
                                 str(message), line)
#


# Parser is instantiated as follows: inst = Parser(fh)
# fh is an open file object
class Parser(object):
   def __init__(self, fh):
      # It is the parser's responsibility to invoke the scanner whenever a
      # token is required
      self.scanner = Scanner(fh)
   #
   
   # Handles the Start productions:
   # Start ::= ( Expr Start
   # Start ::= control_token Control Start
   # Start ::= eof
   def parse_start(self):
      trace('enter parse_start')
      eof = False
      outer_tree = []
      parse_continue = True
      
      tok = self.scanner.scan()
      toktype = tok[0]
      tokline = tok[2]
      dbg('token: ' + str(tok))
      
      if toktype == SCAN_TYPES['LDELIM']:
         dbg('MATCH: Start ::= ( Expr Start')
         # See left paren: implies subtree
         # Therefore parse_expr needs to return a list
         outer_tree.append(self.parse_expr())
      elif toktype == SCAN_TYPES['EOF']:
         dbg('MATCH: Start ::=')
         eof = True
      elif toktype == SCAN_TYPES['CTRL']:
         dbg('MATCH: Start ::= Control-Seq Start')
         outer_tree.append(self.parse_control(tok))
      else:
         trace('leave parse_start by exception')
         raise ParserException(tok[1], tokline)
      dbg('produced parse tree: %s' % str(outer_tree))
      trace('leave parse_start')
      return (outer_tree, eof)
   #

   # Handles the Expr productions:
   # Expr ::= )
   # Expr ::= operator Arg-List
   # Expr ::= ( Expr )
   def parse_expr(self):
      trace('enter parse_expr')
      retval = []
      tok = self.scanner.scan()
      toktype = tok[0]
      dbg('token: ' + str(tok))
      if toktype == SCAN_TYPES['RDELIM']:
         dbg('MATCH: Expr ::=)')
         # Do nothing: retval already []
         pass

      elif toktype == SCAN_TYPES['OPER']:
         dbg('MATCH: Expr ::= operator Arg-List )')
         
         # Insert the operator
         retval.append(tok)

         # TRICK: pass retval to parse_arglist (by reference), so that
         # further methods can add leaf nodes to this level of the tree
         self.parse_arglist(retval)
      elif toktype == SCAN_TYPES['LDELIM']:
         dbg('MATCH: Expr ::= ( Expr )')
         retval.append(self.parse_expr())
         # Check for required right delimiter
         chktok = self.scanner.scan()
         chktype = chktok[0]
         if chktype != SCAN_TYPES['RDELIM']:
            trace('leave parse_expr by exception')
            raise ParserException(chktok[1], chktok[2])
      else:
         dbg('NO MATCH!')
         trace('leave parse_expr by exception')
         raise ParserException(tok[1], tok[2])
      dbg('parse_expr generated tree: %s' % str(retval))
      trace('leave parse_expr')
      return retval
   #


   # Handles the Arg-List productions:
   # Arg-List ::= ( Expr Arg-List
   # Arg-List ::= name|integer Arg-List
   # Arg-List ::= )
   #
   # TRICK:
   # arglist puts leaves (or subtrees) directly into out_list, appending
   # left to right in the order that tokens are seen.
   def parse_arglist(self, out_list):
      trace('enter parse_arglist')
      tok = self.scanner.scan()
      toktype = tok[0]
      dbg('token: ' + str(tok))

      while True:
         if toktype == SCAN_TYPES['LDELIM']:
            dbg('MATCH: Arg-List ::= ( Expr Arg-List')
            out_list.append(self.parse_expr())
            # continue in loop: allows the right-recursive Arg-List following
            # an Expr

         elif toktype in (SCAN_TYPES['INT'], SCAN_TYPES['NAME']):
            dbg('MATCH: Arg-List ::= <integer> Arg-List')
            out_list.append(tok)
            # continue in loop: allows the right-recurive Arg-List in rule

         elif toktype == SCAN_TYPES['RDELIM']:
            dbg('MATCH: Arg-List ::= )')
            break     # exit loop: no right recursion for this rule

         else:
            dbg('NO MATCH')
            trace('leave parse_arglist by exception')
            raise ParserException(tok[1], tok[2])
         #

         tok = self.scanner.scan()
         toktype = tok[0]
         dbg('token: ' + str(tok))
      dbg('leave parse_arglist')
      # No return: out_list functions as an output parameter
   #
   
   # Handles the control production:
   # Control ::= name name|integer
   def parse_control(self, control_token):
      trace('enter parse_control')
      control_struct = [ control_token ]
      tok = self.scanner.scan()
      toktype = tok[0]
      dbg('token at first scan: %s' % str(tok))
      if toktype == SCAN_TYPES['NAME']:
         control_struct.append(tok)
         tok = self.scanner.scan()
         toktype = tok[0]
         dbg('token at second scan: %s' % str(tok))
         if toktype in (SCAN_TYPES['NAME'], SCAN_TYPES['INT']):
            dbg('control expression accepted')
            control_struct.append(tok)
         else:
            dbg('token was not an int or name token: syntax error')
            trace('leave parse_control by exception')
            raise ParserException(tok[1], tok[2])
      else:
         dbg('token was not a name token: syntax error')
         trace('leave parse_control by exception')
         raise ParserException(tok[1], tok[2])
      trace('leave parse_control')
      return control_struct
   #

   #
   # Return a tree stored as a list. This method is merely a public wrapper
   # for the Start production, handled by parse_start
   def parse(self):
      return self.parse_start()
#

if __name__ == '__main__':
   from treeprinter import print_tree
   import traceback
   p = None
   filename = '<stdin>'
   if len(sys.argv) > 1:
      filename = sys.argv[1]
      fh = open(filename, 'r')
      p = Parser(fh)
   else:
      print '* Simple LISP Dialect for Teaching :: Parser Component *'
      print ''
      print 'The parser is running in interactive mode. To exit, type'
      print 'CTRL+D (CTRL+Z on Windows) to send the EOF character.'
      print ''
      p = Parser(sys.stdin)

   eof = False   
   code = 0   
   while not eof:
      try:
         tree, eof = p.parse()
         print_tree(tree)
      except KeyboardInterrupt:
         print 'Exiting on signal 2'
         sys.exit(-2)
      except CompilerException, e:
         print filename + ':' + str(e.line) + ': ' + e.message
         code = 2
      except Exception:
         traceback.print_exc()
         code = 2

   sys.exit(code)
#
